package com.sheng.leetcode.year2022.month05.day25;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/05/25
 *
 * 467. 环绕字符串中唯一的子字符串
 *
 * 把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：
 * "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 
 * 现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。 
 *
 * 示例 1:
 *
 * 输入: p = "a"
 * 输出: 1
 * 解释: 字符串 s 中只有一个"a"子字符。
 * 示例 2:
 *
 * 输入: p = "cac"
 * 输出: 2
 * 解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.
 * 示例 3:
 *
 * 输入: p = "zab"
 * 输出: 6
 * 解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。
 *
 * 提示:
 *
 * 1 <= p.length <= 105
 * p 由小写英文字母构成
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/unique-substrings-in-wraparound-string
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0467 {

    @Test
    public void test01(){
//        String p = "a";
//        String p = "cac";
//        String p = "zab";
//        String p = "zaba";
        String p = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz";
        System.out.println(new Solution().findSubstringInWraproundString(p));
    }

}
class Solution {
    public int findSubstringInWraproundString(String p) {
        //获取该字符串的全部子串
//        for (int i = 0; i < p.length(); i++) {
//            for (int j = i + 1; j <= p.length(); j++) {
//                System.out.println(p.subSequence(i, j));
//            }
//        }
        //求以某个字符开始的连续字符串的长度
        //数组下标加上'a'为a字符开头的字符串的长度，值为长度
        int[] ints = new int[26];
        //返回的子串的数量
        int result = 0;
        for (int i = 0; i < p.length(); i++) {
            //count代表以某个字符开头的字符串的长度
            int count = 1;
            int index = p.charAt(i);
            for (int j = i + 1; j < p.length(); j++) {
                if (p.charAt(j) - index == 1 || p.charAt(j) - index == -25) {
                    count++;
                    //将后一个结点赋给index，然后与再后一个结点判断
                    index = p.charAt(j);
                } else {
                    //不满足条件则代表已经不是连续的字符串了，跳出当前循环
                    break;
                }
            }
            //比较前一个a开头的和后一个a开头的字符串的长度
            ints[p.charAt(i) - 'a'] = Math.max(ints[p.charAt(i) - 'a'], count);
        }
        //加起来求总数
        for (int anInt : ints) {
            result += anInt;
        }
        return result;
    }
}
